package leetcode.dp;

/**
 * 当coins[i-1] <= j时证明该硬币是可以参与组合的，当此硬币拿来一个进行组合时，金额还剩 j-coins[i-1]，那么金额**j-coins[i-1]**的组合情况为
 * dp[j-coins[i-1]]，这就是最优子结构。请考虑这样一种情况，当j=coins[i-1]时，如果此时dp[i][j-coins[i-1]]=0，那么肯定是不正确的，所以才需要把第二列的值全部赋为1。 当然这只是coins[i-1]的所有组合情况，还没有算上以前的硬币组和情况，需要加上dp[i-1][j]
 *
 * @author mazouri
 * @create 2021-09-17 9:27
 */
public class _518_change {
    public int change(int amount, int[] coins) {
       int[][] dp = new int[coins.length+1][amount+1];

        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = 1;
        }

        for (int i = 0; i < dp[0].length; i++) {
            dp[0][i] = 0;
        }

        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                if (coins[i-1]>j) dp[i][j] = dp[i-1][j];
                else dp[i][j] = dp[i][j-coins[i-1]]+dp[i-1][j];
            }
        }

       return dp[coins.length][amount];
    }
}
